package code;

public class Code115 {
	
	/*
	 * dp[i][j]表示状态，s的前i的字符变成，t的前j个字符的个数
	 * dp[i][j]=dp[i-1][j]+dp[i][j]|(s[i]==t[j])
	 */
    public int numDistinct(String s, String t) {
    	int n=s.length();
    	int m=t.length();
    	int[][] dp=new int[n+1][m+1];
    	int i,j;
    	//当t是空串，而s不是串，dp[0~n][0]=1
    	for(i=0;i<=n;i++)
    		dp[i][0]=1;
    	//当s是空串，t不是空串，dp[0][0~m]=1;
    	for(i=1;i<=m;i++)
    		dp[0][i]=0;
    	
    	for(i=1;i<=n;i++)
    		for(j=1;j<=m;j++){
    			dp[i][j]=dp[i-1][j];
    			if(s.charAt(i-1)==t.charAt(j-1)){
    				dp[i][j]+=dp[i-1][j-1];
    			}
    		}
        return dp[n][m];
    }
    public static void main(String[] args){
    	String s="rabbbit";
    	String t="rabbit";
    	System.out.println(new Code115().numDistinct(s, t));
    }
}
